1. Field of the Invention
The invention relates generally to computer systems and more particularly to systems and methods for scheduling the processing of tasks in a multiprocessor system to enable real-time processing of data with improved utilization of processing resources.
2. Related Art
As the development of computers and computer-related technologies has advanced, applications for these technologies have advanced at an equally rapid pace. Applications for computer technologies take advantage of increases in processing speed and computational power, and drive the demand for additional increases. The demand for increased speed and power is sometimes met by simply providing additional resources and, and other times, by making the existing resources more efficient.
One of the approaches that is used to provide more computational power is to provide multiple processors in a computer system. By making more processors available to perform the various tasks of a given application, and by having the processors perform the different tasks in parallel, the application can be executed more quickly than if the tasks of the application had to be performed serially by a single processor having comparable processing power.
It is, however, typically more difficult to process the tasks of an application in parallel than to process these tasks serially. Traditionally, applications (computer programs) have been constructed in a serial fashion. In other words, the application consists of a series of program instructions that are executed one after the other. In many instances, one task (e.g., a program instruction or series of instructions) must be completed so that the result of the task can be used for another task. The application is therefore typically serial in nature. There may, however, be some tasks that are independent of each other and can therefore be performed in parallel.
It is often a very complicated and difficult undertaking to determine how the various tasks within an application can be distributed among multiple processors so that the tasks can, to the extent possible, be performed in parallel. As noted above, one of the complications involves determining which tasks are independent of each other and can therefore be performed in parallel. Another complication is that some of the tasks may have processing constraints that may or may not be capable of being satisfied if the tasks are processed in a parallel fashion. For instance, some tasks may be critical to the application and the overall performance of the application may not be acceptable if these tasks are delayed (e.g., in scheduling the tasks for parallel execution.)
One example of a situation in which there are constraints on the execution of tasks within an application is the case in which the application is intended to perform real-time processing of data, such as video data. It is important in the processing of encoded video data that the decoding and presentation of the data to a user (in the form of a video display) be performed in real-time. In other words, the data for the video frames, which represent a video image that has an inherent, real-time speed, must be processed quickly enough that the video image can be presented to the user as a continuous stream at this real-time speed. If there are delays in processing, the video data stream presented to the user will be interrupted, causing interruptions or artifacts in the displayed video. Such interruptions or artifacts are unacceptable, so it is critical to provide real-time processing of the encoded video data.
In order to process data such as encoded video in real-time, the processors in a multiprocessor computing system are scheduled to handle the various processing tasks that are required. The scheduling of these tasks is typically performed in one of two ways—statically, or dynamically. Each of these approaches has its own advantages and disadvantages.
The static scheduling of tasks generally consists of determining the specific tasks that have to be performed and then determining a schedule for execution of these tasks by the different processors, such that the scheduled tasks can be performed in real-time, even in a worst-case scenario. Once this schedule is determined, it is fixed and does not change once processing of the data has begun. The advantages of static scheduling approaches are that they are relatively easy to implement, they are predictable, and they are scalable. The primary disadvantage of static scheduling approaches is that they may have lower utilization of the processors than dynamic approaches.
The dynamic scheduling of tasks generally consists of identifying a processor that is not busy, and assigning the next task to be performed to that processor. In other words, each processor is assigned a corresponding task and, when a particular processor completes its assigned task, a new task is assigned to that processor for execution. The advantage of using a dynamic approach is that utilization of the processors is typically higher than for a static scheduling method. The disadvantages of dynamic scheduling methods is that they are typically more difficult to implement than static scheduling methods, they are not as predictable as static methods (e.g., in terms of dispatch time, rescheduling time, etc.,) and today generally are not easily scalable.